深入剖析Linux内核反向映射机制
作者简介
Cheetah，曾为U-boot社区和Linux内核社区提交过若干补丁，主要从事Linux相关系统软件开发工作，负责Soc芯片BringUp及系统软件开发，喜欢阅读内核源代码，在不断的学习和工作中深入理解内存管理，进程调度，文件系统，设备驱动等内核子系统。
为了系统的安全性，Linux内核将各个用户进程运行在各自独立的虚拟地址空间，用户进程之间通过虚拟地址空间相互隔离，不能相互访问，一个进程的奔溃不会影响到整个系统的异常也不会干扰到系统以及其他进程运行。
Linux内核可以通过共享内存的方式为系统节省大量内存，例如fork子进程的时候，父子进程通过只读的方式共享所有的私有页面。再比如通过IPC共享内存方式，各个不相干的进程直接可以共享一块物理内存等等。
我们都知道操作系统开启mmu之后cpu访问到的都是虚拟地址，当cpu访问一个虚拟地址的时候需要通过mmu将虚拟地址转化为物理地址，这叫做正向映射。而与本文相关的是反向映射，它主要是通过物理页来找到共享这个页的所有的vma对应的页表项，这是本文讨论的问题。
本文目录：
1.反向映射的发展
2.反向映射应用场景
3.匿名页的反向映射
4.文件页的反向映射
5.ksm页的反向映射
5.总结
注：反向映射机制是Linux内核虚拟内存管理的难点也是理解内存管理的关键技术之一！！
1.反向映射的发展
实际上在早期的Linux内核版本中是没有反向映射的这个概念的，那个时候为了找到一个物理页面对应的页表项就需要遍历系统中所有的mm组成的链表，然后对于每一个mm再遍历每一个vma，然后查看这个vma是否映射了这页，这个过程极其漫长而低效，有的时候不得不遍历完所有的mm然后才能找映射到这个页的所有pte。
后来人们发现了这个问题，就再描述物理页面的page结构体中增加一个指针的方式来解决，通过这个指针来找到一个描述映射这个页的所有pte的数组结构，这对于反向映射查找所有pte易如反掌，但是带来的是浪费内存的问题。
接着就在2.6内核的时候，内核大神们想到了复用page结构中的mapping字段，然后通过红黑树的方式来组织所有映射这个页的vma,形成了匿名页和文件页的反向映射机制。
如下为匿名页反向映射图解：
如下为文件页反向映射图解：
但是后来匿名页的反向映射遇到了效率和锁竞争激烈问题，就促使了目前使用的通过avc的方式联系各层级反向映射结构然后将锁的粒度降低的这种方式。可以看到反向映射的发展是伴随着Linux内核的发展而发展，是一个不断进行优化演进的过程。
2.反向映射应用场景
那么为何在Linux内核中需要反向映射这种机制呢？它究竟为了解决什么样的问题而产生的呢？
试想有如下场景：
（1）一个物理页面被多个进程的vma所映射，系统过程中发生了内存不足，需要回收一些页面，正好发现这个页面是适合我们回收利用的，我们能够直接把这个页面还给伙伴系统吗？答案肯定是不能。因为这个页面被很多个进程所共享，我们必须做的事情就是断开这个页面的所以映射关系，这就是反向映射所做的事情。
（2）一些情况我们需要将一个页面迁移到另一个页面，但是牵一发而动全身，可能有一些进程已经映射这个即将要迁移的页面到自己的vma中，那么这个时候同样需要我们知道究竟这个页面被哪些vma所映射呢？这同样是反向映射所做的事情。
实际上，反向映射的主要应用场景为内存回收和页面迁移，当系统发生内存回收和页面迁移的时候，对于每一个候选页Linux内核都会判断是否为映射页，如果是，就会调用try_to_unmap 来解除页表映射关系，本文也主要来从try_to_unmap函数来解读反向映射机制。
如果我们在细致到其他的内核子系统会发现，在内存回收，内存碎片整理，CMA, 巨型页，页迁移等各个场景中都能发现反向映射所做的关键性的工作，所有理解反向映射机制在Linux内核中的实现是理解掌握这些子系统的基础和关键性所在，否则你即将不能理解这些技术背后的脊髓所在，所以说理解反向映射这种机制对于理解Linux内核内存管理是至关重要的！！！
3.匿名页的反向映射
匿名页的共享主要发生在父进程fork子进程的时候，父fork子进程时，会复制所有vma给子进程，并通过调用dup_mmap->anon_vma_fork建立子进程的rmap以及和长辈进程rmap关系结构：
主要通过anon_vma这个数据结构体中的红黑树将共享父进程的页的所有子进程的vma联系起来（通过anon_vma_chain 来联系对应的vma和av），当然这个关系建立比较复杂，涉及到vma,avc和av这些数据结构体。.
而在缺页异常do_anonymous_page的时候将page和vma相关联。
当内存回收或页面迁移的时候，内核路径最终会调用到：
try_to_unmap //mm/rmap.c
->rmap_walk
->rmap_walk_anon
->anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root,pgoff_start, pgoff_end)
->rwc->rmap_one
->try_to_unmap_one
对于候选页，会拿到候选页相关联的anon_vma，然后从anon_vma的红黑树中遍历到所有共享这个页的vma，然后对于每一个vma通过try_to_unmap_one来处理相对应的页表项，将映射关系解除。
4.文件页的反向映射
文件页的共享主要发生在多个进程共享libc库，同一个库文件可以只需要读取到page cache一次，然后通过各个进程的页表映射到各个进程的vma中。
管理共享文件页的所以vma是通过address_space的区间树来管理，在mmap或者fork的时候将vma加入到这颗区间树中：
发生文件映射缺页异常的时候，将page和address_space相关联。
当内存回收或页面迁移的时候，内核路径最终会调用到：
try_to_unmap //mm/rmap.c
->rmap_walk
->rmap_walk_file
->vma_interval_tree_foreach(vma, &mapping>i_mmap,pgoff_start, pgoff_end)
->rwc->rmap_one
对于每一个候选的文件页，如果是映射页，就会遍历page所对应的address_space的区间树，对于每一个满足条件的vma，调用try_to_unmap_one来找到pte并解除映射关系。
5.ksm页的反向映射
ksm机制是内核将页面内容完全相同的页面进行合并（ksm管理的都是匿名页），将映射到这个页面的页表项标记为只读，然后释放掉原来的页表，来达到节省大量内存的目的，这对于host中开多个虚拟机的应用场景非常有用。
ksm机制中会管理两课红黑树，一棵是stable tree,一棵是unstable tree，stable tree中的每个节点stable_node中管理的页面都是页面内容完全相同的页面（被叫做kpage）,共享kpage的页面的页表项都会标记为只读，而且对于原来的候选页都会有rmap_item来描述他的反向映射（其中的anon_vma成员的红黑树是描述映射这个候选页的所有vma的集合），合并的时候会加入到对应的stable tree节点和链表中。
当内存回收或页面迁移的时候，内核路径最终会调用到：
try_to_unmap //mm/rmap.c
->rmap_walk
->rmap_walk_ksm //mm/ksm.c
-> hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist)
->anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root,0, ULONG_MAX)
->rwc->rmap_one
对于一个ksm页面，反向映射的时候，会拿到ksm页面对应的节点，然后遍历节点的hlist链表，拿到每一个anon_vma，然后就和上面介绍的匿名页的反向映射一样了，从anon_vma的红黑树中找到所有的vma，最后try_to_unmap_one来找到pte并解除映射关系。
6.总结
前面我们介绍了反向映射的三种类型，匿名页，文件页和ksm页的反向映射,分别通过page所对应的的vma, address_space, stable_node结构来查找vma。当然我们只是介绍了Linux内核中的反向映射的冰山一角，主要是try_to_unmap函数，其实每种反向映射各个数据结构建立的过程错综复杂，一篇文章三言两语也说不清楚，他们散落在Linux内核源代码的进程创建fork，内存映射mmap,缺页异常处理，文件系统等各个角落。
诚然，如果我们搞不清楚各种反正映射所对应的各种数据结构之间的关系，或者只是有一些概念上的了解，并没有真正掌握这种机制的实现原理，对于我们来理解Linux内核虚拟内存管理来说是一种障碍，不懂得反向映射内存管理 中的很多问题是搞不明白的！
（END）
更多精彩，尽在"Linux阅码场"，扫描下方二维码关注